#include "main/utils.h"
using namespace std;

int maxProduct_solution1(const vector<string> &input) {
  int max_product = 0;
  for (int i = 0; i < input.size(); ++i) {
    for (int j = i + 1; j < input.size(); ++j) {
      string tmp;
      set_intersection(input[i].begin(), input[i].end(),
                       input[j].begin(), input[j].end(),
                       inserter(tmp, tmp.begin()));
      if (tmp.empty()) {
        auto product = input[i].length() * input[j].length();
        if (product > max_product) {
          max_product = product;
        }
      }
    }
  }
  return max_product;
}

int maxProduct_solution2(const vector<string> &input) {
  vector<int> hash(input.size(), 0);
  for (int i = 0; i < input.size(); ++i) {
    for (int j = 0; j < input[i].size(); ++j) {
      hash[i] |= (1 << (input[i][j] - 'a'));
    }
  }

  int max_product = 0;
  for (int i = 0; i < input.size(); ++i) {
    for (int j = i + 1; j < input.size(); ++j) {
      if ((hash[i] & hash[j]) == 0) {
        int tmp_product = input[i].length() * input[j].length();
        if (tmp_product > max_product) {
          max_product = tmp_product;
        }
      }
    }
  }

  return max_product;
}

int main() {
  vector<string> input = {"abcw", "foo", "bar", "fxyx", "abcdef"};
  int ret = maxProduct_solution1(input);
  cout << "The maximum product is(solution1): " << ret << endl;

  ret = maxProduct_solution2(input);
  cout << "The maximum product is(solution2): " << ret << endl;

  return 0;
}
